//
//  main.c
//  kmp
//
//  Created by zhangnan on 2025/6/17.
//

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/*
 暴力匹配
 */
int strStr(char* haystack,char* needle);

/*
 kmp 算法
 */
int kmpStr(char* haystack,char* needle);

/*
 计算next 数组
 */
void cal_next(char* needle,int *next);


int main(int argc, const char * argv[]) {

    char *h1="abcaabdaabc";
    char *h2="ababaa";
    printf("%d\n",strStr(h1, h2));
    
    printf("%d\n",kmpStr(h1, h2));
    

    return 0;
}

/*
 暴力匹配
 */
int strStr(char* haystack,char* needle){
    int result=-1;
    int len_origin=strlen(haystack);
    int len_compare=strlen(needle);
    int i=0;
   
    while(i<=len_origin-len_compare)
    {
        int j=0;
        while(j<len_compare&&j!=-1)
        {
            if(haystack[i]==needle[j])
            {
                i++;
                j++;
            }else
            {
                i=i-j+1;
                j=-1;
            }
        }
        
        if (j!=-1)
        {
            return i-j;
        }
    }
    return result;
}


/*
 计算next 数组
 */
void cal_next(char* needle,int *next)
{
    int len_needle=strlen(needle);
    
    //待实现
}


/*
 kmp 算法
 */
int kmpStr(char* haystack,char* needle)
{
    int len_needle=strlen(needle);
    int len_haystack=strlen(haystack);
    int* next=(int *)malloc(len_needle*sizeof(int));
    cal_next(needle, next);
    printf("next array is:");
    for(int m=0;m<len_needle;m++)
    {
        printf("%d ",next[m]);
    }
    printf("\n");
    int i=0;
    int j=0;
    while(i<len_haystack&&j<len_needle)
    {
        if(haystack[i]==needle[j])
        {
            i++;
            j++;
        }
        else
        {
            if(j==0)
            {
                i++;
            }
            else
            {
                j=next[j];
            }
            
        }
    }
    if (j==len_needle)
    {
      return i-j;
    }
    else
    {
        return -1;
    }
    
}
